package leetcode_800;

import java.util.Arrays;

/**
 *@author 周杨
 *DeleteAndEarn_740_  给定一个数组 每次删除一个数 把其相邻的数删除 获得这个数的积分 问获得最大的积分
 *describe:抢房子问题的延伸 可以用值的累加代替房子 动态规划AC 87%
 *2018年10月15日 下午3:55:05
 */
public class DeleteAndEarn_740_ {
	
	public static void main(String[] args) {
		DeleteAndEarn_740_ test=new DeleteAndEarn_740_();
		System.out.println(test.deleteAndEarn(new int[] {10,8,4,2,1,3,4,8,2,9,10,4,8,5,9,1,5,1,6,8,1,1}));
	}
	
	/**
	 * describe:动态规划 AC 87%
	 * 2018年10月15日 下午3:46:30
	 */
	public int deleteAndEarn(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int max = 0;
        for (int num: nums) max = Math.max(max, num);//找到最大值 
        int[] dp = new int[max+1];
        
        for (int num: nums) dp[num] += num;//开始积累这个int 出现的总和  完全变成了抢劫房子的问题 不必排序了
        
        for (int i = 2; i <= max; i++) dp[i] = Math.max(dp[i] + dp[i-2], dp[i-1]);
        return dp[max];
    }
	
	/**
	 * describe:[1,1,1,1,1,2,2,3,4,4,4,5,5,6]会要注意 因为可以跳两步选择 常规解法 AC 60%
	 * 2018年10月15日 下午3:37:51
	 */
	public int deleteAndEarn1(int[] nums) {
		if(nums.length==0)
			return 0;
		if(nums.length==1)
			return nums[0];
        Arrays.sort(nums);
        int delete=nums[0],nodelete=0;
        int temp;
        for(int i=1;i<nums.length;++i) {
        	if(nums[i-1]==nums[i]) {//如果与原来的相同 
        		delete+=nums[i];//那么继续删除肯定收益最大 因为两边的删光了 不删是傻子
        	}
        	else {//那么现在的比原来大
        		if(nums[i]==nums[i-1]+1) {//如果现在的是原来删过的
        			temp=nodelete;
        			nodelete=Math.max(delete, nodelete);//删不掉
        			delete=nums[i]+temp;
        		}
        		else {//可以删
        			temp=Math.max(delete, nodelete);
        			delete=temp+nums[i];//因为两者都可以删除
        			nodelete=temp;
        		}
        	}
        }
        return Math.max(nodelete, delete);
    }
}
